#include<stdio.h>

// 无向图的邻接矩阵实现
#define false 0
#define true 1
#define maxNumber 100

typedef struct
{
    char vexs[maxNumber];   //顶点表
    int arcs[maxNumber][maxNumber]; 
    int vexNum,arcNum;  // 图的点数、边数
}AMGraph;

int Location(AMGraph* graph,char c)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        if(graph->vexs[i]==c)
        {
            return i;
        }
    }
    return -1;
}

void creatUNM(AMGraph* graph,int countX)
{
    //countx 为节点的个数
    char buff[10];
    int count=0;
    FILE* f=fopen("./ax1.txt","r");
    
    while(fgets(buff,10,f)!=NULL)
    {
        count++;
    }
    fseek(f,0,SEEK_SET);
    graph->vexNum=countX;
    graph->arcNum=count-countX;

    for(int i=0;i<countX;i++)
    {
        fgets(buff,10,f);
        graph->vexs[i]=buff[0];  //载入顶点信息
    }
    for(int i=0;i<maxNumber;i++)
    {
        for(int j=0;j<maxNumber;j++)
        {
            graph->arcs[i][j]=0;  // 邻接矩阵初始化
        }
    }

    int v1,v2;   // 临时记录两个顶点的位置信息
    for(int i=0;i<(count-countX);i++)
    {
        fgets(buff,10,f);
        v1=Location(graph,buff[0]);
        v2=Location(graph,buff[2]);

        // 记录边的信息
        graph->arcs[v1][v2]=1;
        graph->arcs[v2][v1]=1; 
    }
    fclose(f);
    // printf("count=%d\n",count);
    // while(fgets(buff,10,f)!=NULL)
    // {
    //     printf("%s",buff);
    // }
}

// 深度优先遍历,递归实现
void deepSearchTu(AMGraph* graph,int* visited,int index)
{
    visited[index]=1;
    printf("%c\t",graph->vexs[index]);
    for(int i=0;i<graph->vexNum;i++)
    {
        if((graph->arcs[index][i]!=0)&&(visited[i]!=1))
        {
            deepSearchTu(graph,visited,i);
        }
    }
}

int Stackpoint=-1;
void StackPush(char* chs,char c)
{
    chs[++Stackpoint]=c;
}
char StackPop(char* chs)
{
    return chs[Stackpoint--];
}
int judgeOK(int* ins,int len)
{
    for(int i=0;i<len;i++)
    {
        if(ins[i]==0)
            return true;
    }
    return false;
}

int IntStackpoint=-1;
void IntStackPush(int* chs,int c)
{
    chs[++IntStackpoint]=c;
}
int IntStackPop(int* chs)
{
    return chs[IntStackpoint--];
}


void showStack(char* chs)
{
    char mychs[5];
    int size=5;
    printf("\n堆栈深度优先遍历的展示\n");
    while(Stackpoint!=-1)
    {
        mychs[--size]=StackPop(chs);
        // printf("%c\t",StackPop(chs));
    }
    for(int i=0;i<5;i++)
    {
        printf("%c\t",mychs[i]);
    }
}

int myJudge(char* chs,char c,int len)
{
    for(int i=0;i<len;i++)
    {
        if(chs[i]==c)
        {
            return false;
        }
    }
    return true;
}
// 深度优先遍历，堆栈实现
void deepSearchByStack(AMGraph* graph,int begin)
{
    int StackVisited[5]={0};
    char StackChars[5];
    int IntStack[5];
    int i,j=0;

    for(i=0;i<5;i++)
    {
        StackChars[i]='0';
    }

    StackPush(StackChars,graph->vexs[begin]);
    while(judgeOK(StackVisited,5))
    {
        StackVisited[begin]=1;
        for(i=0;i<graph->vexNum;i++)
        {
            if((graph->arcs[begin][i]!=0)&&(StackVisited[i]!=1)&&myJudge(StackChars,graph->vexs[i],5))
            {
                StackPush(StackChars,graph->vexs[i]);
                IntStackPush(IntStack,begin);
                begin=i;
                break;
            }
        }
        if (i==graph->vexNum)
        {
            int mycount=0;
            for(int j=0;j<graph->vexNum;j++)
            {
                char c1=StackChars[j];
                // printf("\n%c --> %c",c1,graph->vexs[begin]);
                if(graph->vexs[begin]==c1 )
                {
                    mycount=1;
                    break;
                }
            }
            if(mycount==0)
            {
                StackPush(StackChars,graph->vexs[begin]);
            }

            begin=IntStackPop(IntStack);
        }
        
    }
    showStack(StackChars);
}

void main()
{
    AMGraph graph;
    int rootCount=5; // 结点个数
    creatUNM(&graph,rootCount);
    int visited[5]={0};
    deepSearchTu(&graph,visited,1);
    deepSearchByStack(&graph,1);
}